/* 莫队 O(n*sqrt(m))
    离线算法 分块+暴力
* 1.暴力做法
    记录一个 cnt[x] 数组，表示当前区间 x 出现的次数，
    在两个区间转移时，即左右指针分别移动到对应区间的同时更新 cnt[x]，同时更新答案

* 2.分块策略：将所有区间按左端点分块，同时块内的区间右端点排序再暴力求解

* 3.玄学优化
    对于奇数块内部右端点按照从小到大排序，
    对于偶数块内部右端点按照从大到小排序，
    奇数块和偶数块可以互换

    解释:在第一次滚动时，右端点大概率靠右，如果直接右端点再回到左侧重新滚到右，会多滚一次
                                        如果从右向左滚动，只滚动两次
*/
#define DEBUG
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=2e6+10;

inline int read()
{
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x;
}
inline void write(int x)
{
	if (x>=10) write(x/10);
	putchar(x%10+48);
}//快读快输

int n, m, mq, mc, len;
int w[N], cnt[N], res[N];

inline int get(int x)
{
    return x/len;
}

struct Query
{
    int id, l, r;
    int ts; //时间戳
    bool operator<(const Query &q) const {
        int l1 = get(l), r1 = get(r);
        int l2 = get(q.l), r2 = get(q.r);
        if (l1 != l2) return l1 < l2;
        if (r1 != r2) return r1 < r2;
        return ts < q.ts;
    }
} query[N];

struct Modify
{
    int pos, change;
}modi[N];

inline void printonequery(int i)
{
    printf("query[%d]: %d %d %d\n", query[i].id, query[i].l, query[i].r, query[i].ts);
}
inline void printquery()
{
    for(int i=1; i<=mq; i++)
        printonequery(i);
}

inline void printonemodify(int i)
{
    printf("time:%d pos:%d change:%d\n", i, modi[i].pos, modi[i].change);
}
inline void printModify()
{
    for(int i=1; i<=mc; i++)
        printonemodify(i);
}
inline void add(int x, int &res)
{
    res+=!cnt[x]++;
}

inline void del(int x, int &res)
{
    res-=!--cnt[x];
}

void jump(Modify& x, int l, int r, int& res) //时间变化的维护
{
    if (l <= x.pos && x.pos <= r) //区间修改会导致答案改动
    {
        add(x.change, res);
        del(w[x.pos], res);
    }
    swap(x.change, w[x.pos]);
    //因为修改后的下一次操作一定相反(在修改就是改变)，所以只需交换即可，而不需要写两个函数
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
        freopen("./out.txt","w",stdout);
    #endif

    n=read(); m=read();
    for(int i=1; i<=n; i++) w[i]=read();
    
    for(int i=1; i<=m; i++){
        char op[2]; int l, r; 
        scanf("%s", op); 
        l=read(); r=read();
        if(*op=='Q') query[++mq]={mq, l, r, mc};
        else modi[++mc]={l, r};
    } 

    len=cbrt((double)n*max(1, mc)); //开三次方
    sort(query+1, query+1+mq);

    for(int qid=1, i=1, j=0, t=0, ans=0; qid<=mq; qid++) //[i, j]当前的区间
    {
        int l=query[qid].l, r=query[qid].r, ts=query[qid].ts;
        // printf("%d [%d,%d] [%d,%d]\n", qid, l, r, i, j);
        while(j<r) add(w[++j], ans); //右指针移动到当前范围，加入节点
        while(j>r) del(w[j--], ans); //删除多余节点
        while(i<l) del(w[i++], ans); //做指针移动到当前范围，删除节点
        while(i>l) add(w[--i], ans); //加入节点
        while (t < ts) jump(modi[++t], i, j, ans);
        while (t > ts) jump(modi[t--], i, j, ans);//先把修改值还回去在变时间
        res[query[qid].id]=ans;
    }

    for(int i=1; i<=mq; i++)
        write(res[i]), puts(""); //printf("%d\n", res[i]);
    return 0;
}   